\chapter{消息认证码(Message Authentication Code)}
消息认证码是用用于消息认证的，消息认证是一个过程，用来保证接受到消息的真实性(是宣称者发来的)和消息的完整性(未被篡改，插入，删除)，同时还用于验证消息的顺序性和时间性(未重排，重放，延迟)。

\section{MAC定义}
The message authentication code (MAC) is generated from an associated message as a method for assuring the integrity of the message and the authenticity of the source of the message.  A secret key to the generation algorithm must be established between the originator of the message and its intended receiver(s).Currently, there are three (3) approved* general purpose MAC algorithms:  HMAC, KMAC and CMAC.\footnote{Copy from \url{https://csrc.nist.gov/projects/message-authentication-codes}}\par

M是消息，k是密钥，$C_k$是加密函数，t是MAC(也有称为tag的)，$t=C_k(M)$，A要发送M给B，其将$M || t$发送给B，B收到$M' || t'$后，计算$C_k(M')$，如果$t'=C_k(M')$，表示消息是A发的(密钥只有他俩知道)，并且没有被修改，否则表示消息有问题\footnote{大家可以考虑，这里问题指的是什么？完整性和真实性。}。
\section{MAC函数要求}
假设敌手知道C，但不知道密钥k，那么整个MAC系统应该满足：
\begin{itemize}
	\item 敌手知道M和t，构造一个M'，满足$C_k(M')=t$，计算上不可行。
	\item 随机选取两个消息M和M'，两个消息的MAC相等的概率为$2^{-n}$，其中，n为MAC额长度，用公式来表示为$P[C_k(M)=C_k(M'))]=2^{-n}$.
	\item 若M'是M的某个变换，也就是说$M'=f(M)$，那么$P[C_k(M)=C_k(M'))]=2^{-n}$。
\end{itemize}
\section{基于DES的MAC}
可以用对称加密的算法设计MAC码，利用DES算法的CBC模式构造MAC，已被美国的FIPS(Federal Information Processing Standards)采用，FIPS PUB 113,也被美国的ANSI(American National Standards Institute )采用，X9.17。通过CBC对信息加密后，MAC取最后一次的加密输出，或者加密输出的最左M个比特($64 \geq M \geq 16$).
\section{基于哈希函数的MAC(HMAC)}
HMAC是密钥相关的哈希运算消息认证码（Hash-based Message Authentication Code）的缩写，就是利用哈希函数构造MAC的方法，HMAC可以与任何哈希函数(MD5、SHA等)捆绑使用。由H.Krawezyk，M.Bellare，R.Canetti于1996年提出的一种基于Hash函数和密钥进行消息认证的方法，并于1997年作为RFC2104被公布，并在IPSec和其他网络协议（如SSL）中得以广泛应用，现在已经成为事实上的Internet安全标准。\footnote{信息引用自\url{https://baike.baidu.com/item/hmac/7307543?fr=aladdin}}\par
我们对照看看NIST在HMAC引言部分的文字。\par
Providing a way to check the integrity of information transmitted over or stored in an
unreliable medium is a prime necessity in the world of open computing and
communications. Mechanisms that provide such integrity checks based on a secret key
are usually called message authentication codes (MACs). Typically, message
authentication codes are used between two parties that share a secret key in order to
authenticate information transmitted between these parties. This Standard defines a MAC
that uses a cryptographic hash function in conjunction with a secret key. This mechanism
is called HMAC [HMAC]. HMAC shall use an Approved cryptographic hash function
[FIPS 180-3]. HMAC uses the secret key for the calculation and verification of the
MACs.\footnote{引自FEDERAL INFORMATION PROCESSING STANDARDS PUBLICATION (FIPS PUB) 198-1 The Keyed-Hash Message Authentication Code (HMAC) ,July 2008 中的 1.Introduction}\par
\subsection{HMAC方法}
M是根据哈希函数H的要求填充后的消息，对此消息进行分组，每组b位，共分了L组，$m_1,m_2,\ldots,m_L$，n为此哈希函数输出长度。\par

\subsubsection{认证密钥}
选取一个认证密钥K，认证密钥K可以为任意长度，如果K长度大于明文分组的长度b，则将K进行哈希运算，产生长度为n的新密钥，如果K小于分组长度，可以进行填充，在HMAC中直接填充0，填充到长度为b。参与实际后续运算的认证密钥记为$K^+$。

\subsubsection{HMAC计算过程}
HMAC的计算过程，我们用伪代码表示为：\par
\vspace{1cm}
\hspace{2cm} ipad=00110110\par
\hspace{2cm} opad=01011010\par
\hspace{2cm} $S_i=K^+ \oplus ipad$;按位异或\par
\hspace{2cm} $NM1=S_i || m_1 || m_2 || \dots || m_L$ \par
\hspace{2cm} $v_1=H(IV,NM)$\par
\hspace{2cm} $NM2=v_1$填充到长度为b\par
\hspace{2cm} $S_0=K^+ \oplus opad$;按位异或\par
\hspace{2cm} $NM3=S_0 || NM2$;按位异或\par
\hspace{2cm} $v_2=H(IV,NM3)$\par
\hspace{2cm} 算法输出$v_2$\par
\vspace{1cm}

如果我们在HMAC中选用MD5，即H为$H_{MD5}$，那么b=512 bit，n=128 bit，IV=(W,X,Y,Z)。
